package _0583_Delete_Operation_for_Two_Strings;

/**
 * Date: 2021/9/25 10:56
 * Content:
 * 执行用时：5 ms, 在所有 Java 提交中击败了99.51%的用户
 * 内存消耗：39 MB, 在所有 Java 提交中击败了54.93%的用户
 */
public class Solution {

    public int minDistance(String a, String b) {

        char[] as = a.toCharArray(), bs = b.toCharArray();
        int n = a.length(), m = b.length();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (as[i - 1] == bs[j - 1]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
            }
        return n + m - f[n][m] * 2;
    }

    public static void main(String[] args) {

        System.out.println((new Solution()).minDistance("sea", "eat"));  // 2
    }
}
